#include <vector>
#include <queue>
#include <deque>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <iterator>

using namespace std;

struct Entry { 
    int val_;
    int src_;
    Entry( int v, int s ) 
	    : val_(v), 
	      src_(s) {}
};

bool operator<( struct Entry const &a, struct Entry const &b ) {
    return a.val_ > b.val_;
}

void merge( vector< int > &out, vector< deque < int > > &in ) {

    priority_queue< Entry > q;

    for ( unsigned i = 0; i < in.size(); i++ ) {
	if ( in[i].size() ) {
	    q.push( Entry( in[i][0], i ) );
	    in[i].pop_front();
	}
    }

    while ( q.size() ) {
	Entry e( q.top() );
	q.pop();
	out.push_back( e.val_ );
	if ( in[ e.src_ ].size() ) {
	    q.push( Entry( in[ e.src_ ][0], e.src_ ) );
	    in[ e.src_ ].pop_front();
	} 
    }
}

int printIt( vector< deque < int > > const &in ) {
    for ( unsigned i = 0; i < in.size(); i++ ) {
	copy( in[i].begin(), in[i].end(), ostream_iterator<int>( cout, " " ) );
	cout << endl;
    }
    cout << endl;
}

int main ( int argc, char * argv[] ) {
    unsigned m(4), k(10), s(1);
    // cin >> m >> k >> s;
    srand( s );
    
    vector< deque< int > > in;
    for ( unsigned i = 0; i < m; i++ ) {
	deque< int > res;
	for ( unsigned j = 0; j < k; j++ ) {
	    res.push_back( rand() % 10 );
	}
	in.push_back( res );
    }

    printIt( in );

    for ( unsigned i = 0; i < in.size(); i++ ) {
	sort( in[i].begin(), in[i].end() );
    }

    printIt( in );

    vector< int > out;
    merge( out, in );

    for ( unsigned i = 0; i < out.size(); i++ ) {
	cout << out[i] << " ";
    }
    cout << endl;
}
